package com.gitee.wsl.mathematics.geometry.d2.triangle.delaunay

import com.gitee.wsl.mathematics.geometry.d2.line.Line
import com.gitee.wsl.mathematics.geometry.d2.triangle.Triangle
import com.gitee.wsl.mathematics.geometry.d2.triangle.ext.getNoneEdgeVertex
import com.gitee.wsl.mathematics.geometry.d2.triangle.ext.isPointInCircumcircle
import com.gitee.wsl.mathematics.vector.vec2.Vec2f
import kotlin.math.max


/**
 * A Java implementation of an incremental 2D Delaunay triangulation algorithm.
 *
 * @author Johannes Diemke
 */
class DelaunayTriangulator(
   /* *
     * Returns the point set in form of a vector of 2D vectors.
     *
     * @return Returns the points set.*/
    var pointSet: MutableList<Vec2f>?,
) {
    private var triangleSoup: TriangleSoup

    /**
     * Constructor of the SimpleDelaunayTriangulator class used to create a new
     * triangulator instance.
     *
     * @param pointSet
     * The point set to be triangulated
     * @throws NotEnoughPointsException
     * Thrown when the point set contains less than three points
     */

    init {
        this.triangleSoup = TriangleSoup()
    }

    /**
     * This method generates a Delaunay triangulation from the specified point
     * set.
     *
     * @throws com.sdsmdg.kd.trianglify.utilities.triangulator.NotEnoughPointsException
     * */

    @Throws(NotEnoughPointsException::class)
    fun triangulate() {
        triangleSoup = TriangleSoup()

        if (pointSet == null || pointSet!!.size < 3) {
            throw NotEnoughPointsException("Less than three points in point set.")
        }

        /**
         * In order for the in circumcircle test to not consider the vertices of
         * the super triangle we have to start out with a big triangle
         * containing the whole point set. We have to scale the super triangle
         * to be very large. Otherwise the triangulation is not convex.*/

        var maxOfAnyCoordinate = 0.0f

        for (vector in pointSet!!) {
            maxOfAnyCoordinate = max(max(vector.x, vector.y), maxOfAnyCoordinate)
        }

        maxOfAnyCoordinate *= 16.0.toFloat()

        val newCoordinate = 3.0f * maxOfAnyCoordinate
        val p1 = Vec2f(0.0f, newCoordinate)
        val p2 = Vec2f(newCoordinate, 0.0f)
        val p3 = Vec2f(-newCoordinate, -newCoordinate)

        val superTriangle: Triangle = Triangle(p1, p2, p3)

        triangleSoup.add(superTriangle)

        for (i in pointSet!!.indices) {
            val triangle: Triangle? = triangleSoup.findContainingTriangle(pointSet!![i])

            if (triangle == null) {
                /**
                 * If no containing triangle exists, then the vertex is not
                 * inside a triangle (this can also happen due to numerical
                 * errors) and lies on an edge. In order to find this edge we
                 * search all edges of the triangle soup and select the one
                 * which is nearest to the point we try to add. This edge is
                 * removed and four new edges are added.*/

                val edge = triangleSoup.findNearestEdge(pointSet!![i])

                val first = triangleSoup.findOneTriangleSharing(edge)!!
                val second = triangleSoup.findNeighbour(first, edge)!!

                val firstNoneEdgeVertex = first.getNoneEdgeVertex(edge)!!
                val secondNoneEdgeVertex = second.getNoneEdgeVertex(edge)!!

                triangleSoup.remove(first)
                triangleSoup.remove(second)

                val triangle1 = Triangle(edge.a, firstNoneEdgeVertex, pointSet!![i])
                val triangle2 = Triangle(edge.b, firstNoneEdgeVertex, pointSet!![i])
                val triangle3 = Triangle(edge.a, secondNoneEdgeVertex, pointSet!![i])
                val triangle4 = Triangle(edge.b, secondNoneEdgeVertex, pointSet!![i])

                triangleSoup.add(triangle1)
                triangleSoup.add(triangle2)
                triangleSoup.add(triangle3)
                triangleSoup.add(triangle4)

                legalizeEdge(triangle1, Line(edge.a, firstNoneEdgeVertex), pointSet!![i])
                legalizeEdge(triangle2, Line(edge.b, firstNoneEdgeVertex), pointSet!![i])
                legalizeEdge(triangle3, Line(edge.a, secondNoneEdgeVertex), pointSet!![i])
                legalizeEdge(triangle4, Line(edge.b, secondNoneEdgeVertex), pointSet!![i])
            } else {
                /**
                 * The vertex is inside a triangle.*/

                val a: Vec2f = triangle.a
                val b: Vec2f = triangle.b
                val c: Vec2f = triangle.c

                triangleSoup.remove(triangle)

                val first: Triangle = Triangle(a, b, pointSet!![i])
                val second: Triangle = Triangle(b, c, pointSet!![i])
                val third: Triangle = Triangle(c, a, pointSet!![i])

                triangleSoup.add(first)
                triangleSoup.add(second)
                triangleSoup.add(third)

                legalizeEdge(first, Line(a, b), pointSet!![i])
                legalizeEdge(second, Line(b, c), pointSet!![i])
                legalizeEdge(third, Line(c, a), pointSet!![i])
            }
        }

        /**
         * Remove all triangles that contain vertices of the super triangle.*/

        triangleSoup.removeTrianglesUsing(superTriangle.a)
        triangleSoup.removeTrianglesUsing(superTriangle.b)
        triangleSoup.removeTrianglesUsing(superTriangle.c)
    }

   /* *
     * This method legalizes edges by recursively flipping all illegal edges.
     *
     * @param triangle
     * The triangle
     * @param edge
     * The edge to be legalized
     * @param newVertex
     * The new vertex*/

    private fun legalizeEdge(triangle: Triangle, edge: Line, newVertex: Vec2f) {
        val neighbourTriangle: Triangle? = triangleSoup.findNeighbour(triangle, edge)

        /**
         * If the triangle has a neighbor, then legalize the edge
         * */

        if (neighbourTriangle != null) {
            if (neighbourTriangle.isPointInCircumcircle(newVertex)) {
                triangleSoup.remove(triangle)
                triangleSoup.remove(neighbourTriangle)

                val noneEdgeVertex = neighbourTriangle.getNoneEdgeVertex(edge)!!

                val firstTriangle = Triangle(noneEdgeVertex, edge.a, newVertex)
                val secondTriangle = Triangle(noneEdgeVertex, edge.b, newVertex)

                triangleSoup.add(firstTriangle)
                triangleSoup.add(secondTriangle)

                legalizeEdge(firstTriangle, Line(noneEdgeVertex, edge.a), newVertex)
                legalizeEdge(secondTriangle, Line(noneEdgeVertex, edge.b), newVertex)
            }
        }
    }

    /**
     * Creates a random permutation of the specified point set. Based on the
     * implementation of the Delaunay algorithm this can speed up the
     * computation.*/

    fun shuffle() {
        pointSet!!.shuffle()
    }

    /**
     * Shuffles the point set using a custom permutation sequence.
     *
     * @param permutation
     * The permutation used to shuffle the point set*/

    fun shuffle(permutation: IntArray) {
        val temp: MutableList<Vec2f> = ArrayList()
        for (i in permutation.indices) {
            temp.add(pointSet!![permutation[i]])
        }
        pointSet = temp
    }

    val triangles: List<Triangle>
        /**
         * Returns the trianges of the triangulation in form of a vector of 2D
         * triangles.
         *
         * @return Returns the triangles of the triangulation.
         * */

        get() = triangleSoup.triangles
}

/**
 * Exception thrown by the Delaunay triangulator when it is initialized with
 * less than three points.
 *
 * @author Johannes Diemke
 */
class NotEnoughPointsException : Exception {
    constructor()
    constructor(s: String?) : super(s)
}